{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Magic Squares In Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numMagicSquaresInside"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中的幻方"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>3 x 3</code> 的幻方是一个填充有&nbsp;<strong>从 <code>1</code> 到 <code>9</code>&nbsp;</strong> 的不同数字的 <code>3 x 3</code> 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。</p>\n",
    "\n",
    "<p>给定一个由整数组成的<code>row x col</code>&nbsp;的 <code>grid</code>，其中有多少个&nbsp;<code>3 × 3</code> 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/09/11/magic_main.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>\n",
    "下面的子矩阵是一个 3 x 3 的幻方：\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/09/11/magic_valid.jpg\" />\n",
    "而这一个不是：\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/09/11/magic_invalid.jpg\" />\n",
    "总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输出:</strong> grid = [[8]]\n",
    "<strong>输入:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>row == grid.length</code></li>\n",
    "\t<li><code>col == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= row, col &lt;= 10</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [magic-squares-in-grid](https://leetcode.cn/problems/magic-squares-in-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [magic-squares-in-grid](https://leetcode.cn/problems/magic-squares-in-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[4,3,8,4],[9,5,1,9],[2,7,6,2]]', '[[8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    s = (grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1])\n",
    "                    s = ''.join(map(str, s)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = (grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1])\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = [grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1]]\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(1, row-1):\n",
    "            for j in range(1, col-1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = [grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1]]\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(1, row-1):\n",
    "            for j in range(1, col-1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = [grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1]]\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = [grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1]]\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        l = [[8,1,6,3,5,7,4,9,2],[6,1,8,7,5,3,2,9,4],[4,9,2,3,5,7,8,1,6],[2,9,4,7,5,3,6,1,8],[6,7,2,1,5,9,8,3,4],[8,3,4,1,5,9,6,7,2],[2,7,6,9,5,1,4,3,8],[4,3,8,9,5,1,2,7,6]]\n",
    "        count = 0\n",
    "        for i in range(len(grid)-2):\n",
    "            for j in range(len(grid[0])-2):\n",
    "                temp = grid[i][j:j+3]+grid[i+1][j:j+3]+grid[i+2][j:j+3]\n",
    "                if temp in l:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        def check(x, y):\n",
    "            nums = []\n",
    "            for i in range(x-2,x+1):\n",
    "                for j in range(y-2,y+1):\n",
    "                    nums.append(grid[i][j])\n",
    "            if sorted(nums) != list(range(1, 10)): return False\n",
    "            a,b,c,d,e,f,g,h,i = nums\n",
    "            return a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g \n",
    "\n",
    "        for i in range(2, m):\n",
    "            for j in range(2, n):\n",
    "                if check(i, j):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\r\n",
    "        def isMagicSquares(grid: list[list[int]]) -> bool:\r\n",
    "            row, col, diag = [0] * 3, [0] * 3, [0] * 2\r\n",
    "            vis = [0] * 10\r\n",
    "            for i in range(3):\r\n",
    "                for j in range(3):\r\n",
    "                    if grid[i][j] < 1 or grid[i][j] > 9 or vis[grid[i][j]]:\r\n",
    "                        return False\r\n",
    "                    vis[grid[i][j]] = 1\r\n",
    "                    row[i] += grid[i][j]\r\n",
    "                    col[j] += grid[i][j]\r\n",
    "                    if i == j:\r\n",
    "                        diag[0] += grid[i][j]\r\n",
    "                    if i + j == 2:\r\n",
    "                        diag[1] += grid[i][j]\r\n",
    "            return len(set(row + col + diag)) == 1\r\n",
    "        \r\n",
    "        row, col = len(grid), len(grid[0])\r\n",
    "        if row < 3 or col < 3:\r\n",
    "            return 0\r\n",
    "        cnt = 0\r\n",
    "        for i in range(row - 2):\r\n",
    "            for j in range(col - 2):\r\n",
    "                if isMagicSquares([x[j:j+3] for x in grid[i:i+3]]):\r\n",
    "                    cnt += 1\r\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        ret=0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if m<3 or n<3:\n",
    "            return 0\n",
    "        \n",
    "        def dwcx(x,y):\n",
    "            xx=[0]*10\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    if grid[x+i][y+j] <1 or grid[x+i][y+j] >9:\n",
    "                        return False\n",
    "                    xx[grid[x+i][y+j]]=1\n",
    "            for i in range(1,10):\n",
    "                if xx[i]==0:\n",
    "                    return False\n",
    "\n",
    "            s=grid[x][y]+grid[x+1][y+1]+grid[x+2][y+2]\n",
    "            t=grid[x+1][y+1]+grid[x+2][y]+grid[x][y+2]\n",
    "            if s!=t:\n",
    "                return False\n",
    "            for i in range(3):\n",
    "                t=0\n",
    "                w=0\n",
    "                for j in range(3):\n",
    "                    t+=grid[x+i][y+j]\n",
    "                    w+=grid[x+j][y+i]\n",
    "                if t!=s or w!=s:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                if dwcx(i,j):\n",
    "                    ret+=1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n, res = len(grid), len(grid[0]), 0\n",
    "        for a in range(m-2):\n",
    "            for b in range(n-2):\n",
    "                if set(grid[i][j] for i in range(a,a+3) for j in range(b,b+3)) == {1,2,3,4,5,6,7,8,9} and all(grid[i][b] + grid[i][b+1] + grid[i][b+2] == 15 for i in range(a,a+3)) and all(grid[a][i] + grid[a+1][i] + grid[a+2][i] == 15 for i in range(b,b+3)) and grid[a][b] + grid[a+1][b+1] + grid[a+2][b+2] == grid[a][b+2] + grid[a+1][b+1] + grid[a+2][b] == 15: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m < 3 or n < 3:\n",
    "            return 0\n",
    "        S = 15\n",
    "        ans = 0\n",
    "        def judge(x, y):\n",
    "            cnt = [0]*10\n",
    "            for dx in [0, 1, 2]:\n",
    "                s = 0\n",
    "                for dy in [0, 1, 2]:\n",
    "                    if grid[x + dx][y + dy] <= 0 or grid[x + dx][y + dy] > 9:\n",
    "                        return 0\n",
    "                    if cnt[grid[x + dx][y + dy]] > 0:\n",
    "                        return 0\n",
    "                    cnt[grid[x + dx][y + dy]] = 1\n",
    "                    s += grid[x + dx][y + dy]\n",
    "                if s != S:\n",
    "                    return 0\n",
    "            for dy in [0, 1, 2]:\n",
    "                s = 0\n",
    "                for dx in [0, 1, 2]:\n",
    "                    s += grid[x + dx][y + dy]\n",
    "                if s != S:\n",
    "                    return 0\n",
    "            if grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2] != S:\n",
    "                return 0\n",
    "            if grid[x+2][y] + grid[x+1][y+1] + grid[x][y+2] != S:\n",
    "                return 0\n",
    "            return 1\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                ans += judge(i, j)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        def istrue(posx,posy):\n",
    "            l = []\n",
    "            vis = [0]*9\n",
    "            for i in range(3):\n",
    "                re = 0\n",
    "                for j in range(3):\n",
    "                    re += grid[posx+i][posy+j]\n",
    "                    if grid[posx+i][posy+j]<=0 or grid[posx+i][posy+j]>9:\n",
    "                        return False\n",
    "                    vis[grid[posx+i][posy+j]-1] = 1\n",
    "                l.append(re)\n",
    "            if sum(vis) != 9:\n",
    "                return False\n",
    "            for j in range(3):\n",
    "                re = 0\n",
    "                for i in range(3):\n",
    "                    re += grid[posx+i][posy+j]\n",
    "                l.append(re)\n",
    "            i,j = posx,posy\n",
    "            l.append(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2])\n",
    "            l.append(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j])\n",
    "            cur = l[0]\n",
    "            for t in l:\n",
    "                if cur != t:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(len(grid)-2):\n",
    "            for j in range(len(grid[0])-2):\n",
    "                res += istrue(i,j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if m*n<9 or m<3 or n<3:\n",
    "            return 0\n",
    "        ans=0\n",
    "        for row in range(m-2):\n",
    "            for i in range(n-2):\n",
    "                d=[0]*20\n",
    "                for p in range(row,row+3):\n",
    "                    for q in range(i,i+3):\n",
    "                        d[grid[p][q]]+=1\n",
    "                if all(d[t]==1 for t in range(1,10)):\n",
    "                    s=sum(grid[row][i:i+3])\n",
    "                    if s==sum(grid[row+1][i:i+3])==sum(grid[row+2][i:i+3]):\n",
    "                        if sum(grid[j][i] for j in range(row,row+3))==sum(grid[j][i+1] for j in range(row,row+3))==sum(grid[j][i+2] for j in range(row,row+3))==s:\n",
    "                            if sum(grid[row+c][i+c] for c in range(3))==s:\n",
    "                                ans+=1\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(row - 2):\n",
    "            for j in range(col - 2):\n",
    "                t = 0\n",
    "                for m in range(3):\n",
    "                    for n in range(3):\n",
    "                        if grid[i + m][j + n] == 0:\n",
    "                            continue\n",
    "                        t += 1 << (grid[i + m][j + n] - 1)\n",
    "                if t != (1 << 9) - 1:\n",
    "                    continue\n",
    "                if grid[i][j] + grid[i + 1][j] + grid[i + 2][j] == 15 and \\\n",
    "                grid[i][j + 1] + grid[i + 1][j + 1] + grid[i + 2][j + 1] == 15 and \\\n",
    "                grid[i][j + 2] + grid[i + 1][j + 2] + grid[i + 2][j + 2] == 15 and \\\n",
    "                grid[i][j] + grid[i][j + 1] + grid[i][j + 2] == 15 and \\\n",
    "                grid[i + 1][j] + grid[i + 1][j + 1] + grid[i + 1][j + 2] == 15 and \\\n",
    "                grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2] == 15 and \\\n",
    "                grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2] == 15 and \\\n",
    "                grid[i + 2][j] + grid[i + 1][j + 1] + grid[i][j + 2] == 15:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        r=len(grid)\n",
    "        c=len(grid[0])\n",
    "        def magic(a,b,c,d,e,f,g,h,i):\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == [1,2,3,4,5,6,7,8,9] and\n",
    "                (a+b+c == d+e+f == g+h+i == a+d+g ==\n",
    "                 b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "\n",
    "        out=0\n",
    "        for i in range(r-2):\n",
    "            for j in range(c-2):\n",
    "                if grid[i+1][j+1]!=5:\n",
    "                    continue\n",
    "                if magic(grid[i][j],grid[i][j+1],grid[i][j+2],grid[i+1][j],grid[i+1][j+1],grid[i+1][j+2],grid[i+2][j],grid[i+2][j+1],grid[i+2][j+2]):\n",
    "\n",
    "                    out+=1\n",
    "        return out\n",
    "\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        def magic(a, b, c, d, e, f, g, h, i):\n",
    "            return (sorted([a, b, c, d, e, f, g, h, i]) == list(range(1, 10)) and\n",
    "                (a + b + c == d + e + f == g + h + i == a + d + g ==\n",
    "                 b + e + h == c + f + i == a + e + i == c + e + g == 15))\n",
    "        res = 0\n",
    "        for i in range(len(grid) - 2):\n",
    "            for j in range(len(grid[0]) - 2):\n",
    "                if grid[i + 1][j + 1] != 5:\n",
    "                    continue\n",
    "                if magic(grid[i][j], grid[i][j + 1], grid[i][j + 2],\n",
    "                         grid[i + 1][j], grid[i + 1][j + 1], grid[i + 1][j + 2],\n",
    "                         grid[i + 2][j], grid[i + 2][j + 1], grid[i + 2][j + 2]):\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        if m<3 or n<3:\n",
    "            return 0\n",
    "        def ismagic(i,j):\n",
    "            s=set()\n",
    "            su=grid[i][j]+grid[i+1][j]+grid[i+2][j]\n",
    "            for x in range(3):\n",
    "                if grid[i+x][j]+grid[i+x][j+1]+grid[i+x][j+2]!=su:\n",
    "                    return False\n",
    "                if grid[i][j+x]+grid[i+1][j+x]+grid[i+2][j+x]!=su:\n",
    "                    return False\n",
    "            if not(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]==grid[i+2][j]+grid[i+1][j+1]+grid[i][j+2]==su):\n",
    "                return False\n",
    "            for di in range(3):\n",
    "                for dj in range(3):\n",
    "                    s.add(grid[i+di][j+dj])\n",
    "            return s==set([1,2,3,4,5,6,7,8,9])\n",
    "        return sum(1 for i in range(m-2) for j in range(n-2) if ismagic(i,j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = (grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1])\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '27618349' in s[::-1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        \n",
    "        def check(i, j):\n",
    "            vis = [0] * 9\n",
    "            rows = [0] * 3\n",
    "            cols = [0] * 3\n",
    "            for x in range(i, i+3):\n",
    "                for y in range(j, j+3):\n",
    "                    c = grid[x][y]\n",
    "                    if c == 0 or c > 9 or vis[c - 1]: return False\n",
    "                    vis[c - 1] += 1\n",
    "                    rows[x-i] += c\n",
    "                    cols[y-j] += c\n",
    "            v = rows[0]\n",
    "            return all(c == v for c in rows) and all(c==v for c in cols) and grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2] ==v and grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j] == v\n",
    "            \n",
    "            \n",
    "        \n",
    "        for i in range(m):\n",
    "            if i + 2 > m - 1: break\n",
    "            for j in range(n):\n",
    "                if j + 2 > n - 1: continue\n",
    "                if check(i, j):\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                # 只有中心为5才可能是幻方\n",
    "                if grid[i][j] == 5:\n",
    "                # 周围的数按照顺时针或逆时针旋转得到的数列中一定有“27618349”\n",
    "                    l = (grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1], grid[i][j+1],\n",
    "                        grid[i+1][j+1], grid[i+1][j], grid[i+1][j-1], grid[i][j-1])\n",
    "                    s = ''.join(map(str, l)) * 2\n",
    "                    if '27618349' in s or '94381672' in s:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n, res = len(grid), len(grid[0]), 0\n",
    "        for a in range(m-2):\n",
    "            for b in range(n-2):\n",
    "                if grid[a+1][b+1] == 5 and set(grid[i][j] for i in range(a,a+3) for j in range(b,b+3)) == {1,2,3,4,5,6,7,8,9} and all(grid[i][b] + grid[i][b+1] + grid[i][b+2] == 15 for i in range(a,a+3)) and all(grid[a][i] + grid[a+1][i] + grid[a+2][i] == 15 for i in range(b,b+3)) and grid[a][b] + grid[a+1][b+1] + grid[a+2][b+2] == grid[a][b+2] + grid[a+1][b+1] + grid[a+2][b] == 15: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if m < 3 or n < 3:\n",
    "            return 0\n",
    "        \n",
    "        t = list(zip(*grid))\n",
    "        def valid(r,c):\n",
    "            _set = set()\n",
    "            for i in range(r,r + 3):\n",
    "                for j in range(c,c + 3):\n",
    "                    if grid[i][j] in _set or grid[i][j] > 9 or grid[i][j] <= 0:\n",
    "                        return 0\n",
    "                    _set.add(grid[i][j])\n",
    "                    \n",
    "            if sum(grid[r][c:c + 3]) != 15 or sum(grid[r + 1][c:c + 3]) != 15 or sum(grid[r + 1][c:c + 3]) != 15:\n",
    "                return 0\n",
    "            if sum(t[c][r:r + 3]) != 15 or sum(t[c][r:r + 3]) != 15 or sum(t[c][r:r + 3]) != 15:\n",
    "                return 0\n",
    "            if grid[r][c] +grid[r + 1][c + 1] +grid[r + 2][c + 2] != 15 or grid[r + 2][c] +grid[r + 1][c + 1] +grid[r][c + 2] != 15:\n",
    "                return 0\n",
    "            return 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m - 2):\n",
    "            for j in range(n - 2):\n",
    "                ans += valid(i,j)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        # 找每个5为中心的矩阵是否是幻方\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "\n",
    "        def isMagic(centerX,centerY):\n",
    "            count = [0]*9\n",
    "            rightXie = 0\n",
    "            leftXie = 0\n",
    "            # 按行\n",
    "            for i in range(-1,2):\n",
    "                columnSum = 0\n",
    "                rowSum = 0\n",
    "                for j in range(-1,2):\n",
    "                    columnSum+=grid[centerX+i][centerY+j]\n",
    "                    rowSum+=grid[centerX+j][centerY+i]\n",
    "                    if grid[centerX+i][centerY+j]>9:\n",
    "                        return False\n",
    "\n",
    "\n",
    "                    count[grid[centerX+i][centerY+j]-1]+=1\n",
    "                if rowSum!=15 or columnSum!=15:\n",
    "                    return False\n",
    "\n",
    "                leftXie += grid[centerX+i][centerY+i]\n",
    "                rightXie += grid[centerX+i][centerY-i]\n",
    "            if leftXie!=15 or rightXie!=15:\n",
    "                return False\n",
    "            \n",
    "            for c in count:\n",
    "                if c!=1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1,m-1):\n",
    "\n",
    "            for j in range(1,n-1):\n",
    "                if grid[i][j]!=5:\n",
    "                    continue\n",
    "                if isMagic(i,j):\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def magic(a,b,c,d,e,f,g,h,i):\n",
    "            #range()外多加一个list()\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == list(range(1, 10)) and (a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "\n",
    "        ans = 0\n",
    "        #xrange改为range\n",
    "        for r in range(R-2):\n",
    "            for c in range(C-2):\n",
    "                if grid[r+1][c+1] == 5:\n",
    "                    if magic(grid[r][c], grid[r][c+1], grid[r][c+2],\n",
    "                            grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],\n",
    "                            grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]):\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        row = 1\n",
    "        col = 1\n",
    "        res = 0\n",
    "        while row < len(grid) - 1 and col < len(grid[0]) - 1:\n",
    "            if grid[row][col] == 5:\n",
    "                c = grid[row][col]\n",
    "                l = grid[row][col-1]\n",
    "                r = grid[row][col+1]\n",
    "                t = grid[row-1][col]\n",
    "                b = grid[row+1][col]\n",
    "                lt = grid[row-1][col-1]\n",
    "                tr = grid[row-1][col+1]\n",
    "                rb = grid[row+1][col+1]\n",
    "                bl = grid[row+1][col-1]\n",
    "                if sorted([c, l, r, t, b, lt, tr, rb, bl]) == list(range(1, 10)):\n",
    "                    if lt+t+tr == l+c+r == bl+b+rb == 15 and \\\n",
    "                       lt+l+bl == t+c+b == tr+r+rb == 15 and \\\n",
    "                       lt+c+rb == tr+c+bl == 15:\n",
    "                       res += 1\n",
    "            col += 1\n",
    "            if col >=  len(grid[0]) - 1:\n",
    "                row += 1\n",
    "                col = 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def check(i, j):\n",
    "            # 检查值是否为1-9\n",
    "            cur = set()\n",
    "            for a in range(3):\n",
    "                for b in range(3):\n",
    "                    if not 1 <= grid[i+a][j+b] <= 9 or grid[i+a][j+b] in cur:\n",
    "                        return 0\n",
    "                    cur.add(grid[i+a][j+b])\n",
    "            # 检查行列以及对角线之和是否相同\n",
    "            total = set()\n",
    "            # 行\n",
    "            total.add(grid[i][j]+grid[i][j+1]+grid[i][j+2])\n",
    "            total.add(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2])\n",
    "            total.add(grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2])\n",
    "            # 列\n",
    "            total.add(grid[i][j]+grid[i+1][j]+grid[i+2][j])\n",
    "            total.add(grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1])\n",
    "            total.add(grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2])\n",
    "            # 对角线\n",
    "            total.add(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2])\n",
    "            total.add(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j])\n",
    "            return 1 if len(total) == 1 else 0\n",
    "        \n",
    "        # 枚举幻方的左上角\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for x in range(m-2):\n",
    "            for y in range(n-2):\n",
    "                ans += check(x, y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def check(i, j):\n",
    "            # 检查值是否为1-9\n",
    "            cur = set()\n",
    "            for a in range(3):\n",
    "                for b in range(3):\n",
    "                    if not 1 <= grid[i+a][j+b] <= 9 or grid[i+a][j+b] in cur:\n",
    "                        return 0\n",
    "                    cur.add(grid[i+a][j+b])\n",
    "            # 检查行列以及对角线之和是否相同\n",
    "            total = set()\n",
    "            # 行\n",
    "            total.add(grid[i][j]+grid[i][j+1]+grid[i][j+2])\n",
    "            total.add(grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2])\n",
    "            total.add(grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2])\n",
    "            # 列\n",
    "            total.add(grid[i][j]+grid[i+1][j]+grid[i+2][j])\n",
    "            total.add(grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1])\n",
    "            total.add(grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2])\n",
    "            # 对角线\n",
    "            total.add(grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2])\n",
    "            total.add(grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j])\n",
    "            return len(total) == 1\n",
    "        \n",
    "        # 枚举幻方的左上角\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for x in range(m-2):\n",
    "            for y in range(n-2):\n",
    "                ans += check(x, y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def valid(i, j):\n",
    "            if grid[i][j] != 5:\n",
    "                return 0\n",
    "            if 10 != grid[i - 1][j - 1] + grid[i + 1][j + 1]:\n",
    "                return 0\n",
    "            if 10 != grid[i - 1][j + 1] + grid[i + 1][j - 1]:\n",
    "                return 0\n",
    "            for k in range(-1, 2):\n",
    "                for l in range(-1, 2):\n",
    "                    if grid[i + k][j + l] < 1 or grid[i + k][j + l] > 9:\n",
    "                        return 0\n",
    "            s1 = s2 = s3 = s4 = s5 = s6 = 0\n",
    "            for k in range(-1, 2):\n",
    "                s1 += grid[i + k][j - 1]\n",
    "                s2 += grid[i + k][j]\n",
    "                s3 += grid[i + k][j + 1]\n",
    "                s4 += grid[i - 1][j + k]\n",
    "                s5 += grid[i][j + k]\n",
    "                s6 += grid[i + 1][j + k]\n",
    "\n",
    "            return (\n",
    "                1\n",
    "                if s1 == 15\n",
    "                and s2 == 15\n",
    "                and s3 == 15\n",
    "                and s4 == 15\n",
    "                and s5 == 15\n",
    "                and s6 == 15\n",
    "                and not (\n",
    "                    grid[i - 1][j - 1] == 5\n",
    "                    or grid[i + 1][j + 1] == 5\n",
    "                    or grid[i - 1][j + 1] == 5\n",
    "                    or grid[i + 1][j - 1] == 5\n",
    "                )\n",
    "                else 0\n",
    "            )\n",
    "\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                ans += valid(i, j)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        ans, m, n = 0, len(grid), len(grid[0])\n",
    "        for r in range(m - 2):\n",
    "            for c in range(n - 2):\n",
    "                vals, vs, ok = [0 for _ in range(8)], set(), 1\n",
    "                for dr in range(3):\n",
    "                    for dc in range(3):\n",
    "                        if not 0 < grid[r + dr][c + dc] < 10:\n",
    "                            ok = 0\n",
    "                            break\n",
    "                        vs.add(grid[r + dr][c + dc])\n",
    "                        vals[dr] += grid[r + dr][c + dc]\n",
    "                        vals[3 + dc] += grid[r + dr][c + dc]\n",
    "                        if dr == dc: vals[6] += grid[r + dr][c + dc]\n",
    "                        if dr + dc == 2: vals[7] += grid[r + dr][c + dc]\n",
    "                if ok == 0 or len(vs) != 9: continue\n",
    "                val = vals[0]\n",
    "                for v in vals:\n",
    "                    if val != v:\n",
    "                        ok = 0\n",
    "                        break\n",
    "                ans += ok\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def magic(a: int, b: int, c: int, d: int, e: int, f: int, g: int, h: int, i: int) -> bool:\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == list(range(1, 10)) and \n",
    "            (a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(R-2):\n",
    "            for c in range(C-2):\n",
    "                if grid[r+1][c+1] != 5: continue  # optional skip\n",
    "                if magic(grid[r][c], grid[r][c+1], grid[r][c+2],\n",
    "                         grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],\n",
    "                         grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        cnt = 0\n",
    "        if m < 3 or n < 3: return 0\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                if grid[i][j] != 5: continue\n",
    "                if self.isMagicSquare(grid[i - 1][j - 1], grid[i - 1][j], grid[i - 1][j + 1], grid[i][j - 1], grid[i][j], grid[i][j + 1], grid[i + 1][j - 1], grid[i + 1][j], grid[i + 1][j + 1]):\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "    \n",
    "\n",
    "    def isMagicSquare(self, a, b, c, d, e, f, g, h, i):\n",
    "        if sorted([a, b, c, d, e, f, g, h, i]) != [i for i in range(1, 10)]:\n",
    "            return False\n",
    "        if (a + b + c == d + e + f == g + h + i == a + d + g == b + e + h == c + f + i == a + e + i == c + e + g == 15):\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "          \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        m, n, ans = len(grid), len(grid[0]), 0\n",
    "        if m >= 3 and n >= 3:\n",
    "            for i in range(1, m - 1):\n",
    "                for j in range(1, n - 1):\n",
    "                    if grid[i][j] == 5 and set(grid[i-1][j-1:j+2] + grid[i][j-1:j+2] + grid[i+1][j-1:j+2]) == set(range(1,10)) and 15 == sum(grid[i-1][j-1:j+2]) == sum(grid[i][j-1:j+2]) == sum(grid[i+1][j-1:j+2]) == grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1] == grid[i-1][j]+grid[i][j]+grid[i+1][j] == grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1] == grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1] == grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "        '''\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return sum(grid[i][j] == 5 and set(grid[i-1][j-1:j+2] + grid[i][j-1:j+2] + grid[i+1][j-1:j+2]) == set(range(1,10)) and 15 == sum(grid[i-1][j-1:j+2]) == sum(grid[i][j-1:j+2]) == sum(grid[i+1][j-1:j+2]) == grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1] == grid[i-1][j]+grid[i][j]+grid[i+1][j] == grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1] == grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1] == grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1] for i in range(1, m - 1) for j in range(1, n - 1)) if m >= 3 and n >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        m, n, ans = len(grid), len(grid[0]), 0\n",
    "        if m >= 3 and n >= 3:\n",
    "            for i in range(1, m - 1):\n",
    "                for j in range(1, n - 1):\n",
    "                    if grid[i][j] == 5 and set(grid[i-1][j-1:j+2] + grid[i][j-1:j+2] + grid[i+1][j-1:j+2]) == set(range(1,10)) and 15 == sum(grid[i-1][j-1:j+2]) == sum(grid[i][j-1:j+2]) == sum(grid[i+1][j-1:j+2]) == grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1] == grid[i-1][j]+grid[i][j]+grid[i+1][j] == grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1] == grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1] == grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1]:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "        '''\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return sum(grid[i][j] == 5 and set(grid[i-1][j-1:j+2] + grid[i][j-1:j+2] + grid[i+1][j-1:j+2]) == set(range(1,10)) and 15 == sum(grid[i-1][j-1:j+2]) == sum(grid[i][j-1:j+2]) == sum(grid[i+1][j-1:j+2]) == grid[i-1][j-1]+grid[i][j-1]+grid[i+1][j-1] == grid[i-1][j]+grid[i][j]+grid[i+1][j] == grid[i-1][j+1]+grid[i][j+1]+grid[i+1][j+1] == grid[i-1][j-1]+grid[i][j]+grid[i+1][j+1] == grid[i-1][j+1]+grid[i][j]+grid[i+1][j-1] for i in range(1, m - 1) for j in range(1, n - 1)) if m >= 3 and n >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numMagicSquaresInside(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def magic(a,b,c,d,e,f,g,h,i):\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == list(range(1, 10)) and\n",
    "                (a+b+c == d+e+f == g+h+i == a+d+g ==\n",
    "                 b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "        def xrange(x):\n",
    "            now=0\n",
    "            while now<x:\n",
    "                yield now\n",
    "                now+=1\n",
    "        ans = 0\n",
    "        for r in xrange(R-2):\n",
    "            for c in xrange(C-2):\n",
    "                if grid[r+1][c+1] != 5: continue  # optional skip\n",
    "                if magic(grid[r][c], grid[r][c+1], grid[r][c+2],\n",
    "                         grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],\n",
    "                         grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]):\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\r\n",
    "        R, C = len(grid), len(grid[0])\r\n",
    "        if R < 3 or C < 3:\r\n",
    "            return 0\r\n",
    "        ret = 0\r\n",
    "        graph=[8,1,6,7,2,9,4,3]*2\r\n",
    "        dr=[-1,-1,-1,0,1,1,1,0]\r\n",
    "        dc=[-1,0,1,1,1,0,-1,-1]\r\n",
    "        for r in range(1,R-1):\r\n",
    "            for c in range(1,C-1):\r\n",
    "                if grid[r][c]!=5:\r\n",
    "                    continue\r\n",
    "                around=[]\r\n",
    "                for i in range(8):\r\n",
    "                    around.append(grid[r+dr[i]][c+dc[i]])\r\n",
    "                for i in range(8):\r\n",
    "                    if graph[i]==around[0]:\r\n",
    "                        if  around==graph[i:i+8] or around==graph[i+8:i:-1]:\r\n",
    "                            ret+=1\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numMagicSquaresInside(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def magic(a,b,c,d,e,f,g,h,i):\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == list(range(1, 10)) and\n",
    "                (a+b+c == d+e+f == g+h+i == a+d+g ==\n",
    "                 b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "  \n",
    "        ans = 0\n",
    "        for r in range(R-2):\n",
    "            for c in range(C-2):\n",
    "                if grid[r+1][c+1] != 5: continue  # optional skip\n",
    "                if magic(grid[r][c], grid[r][c+1], grid[r][c+2],\n",
    "                         grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],\n",
    "                         grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]):\n",
    "                    ans += 1\n",
    "        return ans\n",
    "class Solution1(object):\n",
    "    def numMagicSquaresInside(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        def magic(a,b,c,d,e,f,g,h,i):\n",
    "            return (sorted([a,b,c,d,e,f,g,h,i]) == list(range(1, 10)) and\n",
    "                (a+b+c == d+e+f == g+h+i == a+d+g ==\n",
    "                 b+e+h == c+f+i == a+e+i == c+e+g == 15))\n",
    "        def xrange(x):\n",
    "            now=0\n",
    "            while now<x:\n",
    "                yield now\n",
    "                now+=1\n",
    "        ans = 0\n",
    "        for r in xrange(R-2):\n",
    "            for c in xrange(C-2):\n",
    "                if grid[r+1][c+1] != 5: continue  # optional skip\n",
    "                if magic(grid[r][c], grid[r][c+1], grid[r][c+2],\n",
    "                         grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],\n",
    "                         grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]):\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m < 3 or n < 3:\n",
    "            return 0\n",
    "        \n",
    "        def isMagicSquare(x, y):\n",
    "            visited = [0 for _ in range(0, 10)]\n",
    "            sumRow = {i:0 for i in range(3)}\n",
    "            sumCol = {i:0 for i in range(3)}\n",
    "            sumDif = {-1:0, 1: 0}\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    num = grid[i+x][j+y]\n",
    "                    if num > 9 or num < 1 or visited[num]:\n",
    "                        return False\n",
    "                    visited[num] = 1\n",
    "                    sumRow[i] += num\n",
    "                    sumCol[j] += num\n",
    "                    if i == j == 1 or (i == 0 and j == 0) or (i == 2 and j == 2): sumDif[1] += num\n",
    "                    if i == j == 1 or (i == 0 and j == 2) or (i == 2 and j == 0): sumDif[-1] += num\n",
    "            target = sumRow[0]\n",
    "            for _, v in sumRow.items():\n",
    "                if v != target:\n",
    "                    return False\n",
    "            for _, v in sumCol.items():\n",
    "                if v != target:\n",
    "                    return False\n",
    "            for _, v in sumDif.items():\n",
    "                if v != target:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                if isMagicSquare(i, j):\n",
    "                    cnt += 1\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:\n",
    "        row=len(grid)\n",
    "        column=len(grid[0])\n",
    "        if row<3 or column<3:\n",
    "            return 0\n",
    "        else:\n",
    "            num=0\n",
    "            for i in range(0,row-2):\n",
    "                for j in range(0,column-2):\n",
    "                    huanfang=1\n",
    "                    ranges=[1,2,3,4,5,6,7,8,9]\n",
    "                    for a in range(i,i+3):\n",
    "                        for b in range(j,j+3):\n",
    "                            if grid[a][b]  not in ranges:\n",
    "                                huanfang=0\n",
    "                            else:\n",
    "                                ranges.remove(grid[a][b])\n",
    "                    if huanfang!=0:   \n",
    "                        sum=grid[i][j]+grid[i+1][j]+grid[i+2][j]\n",
    "                        if grid[i][j+1]+grid[i+1][j+1]+grid[i+2][j+1]==sum:\n",
    "                            if grid[i][j+2]+grid[i+1][j+2]+grid[i+2][j+2]==sum:\n",
    "                                if grid[i][j]+grid[i][j+1]+grid[i][j+2]==sum:\n",
    "                                    if  grid[i+1][j]+grid[i+1][j+1]+grid[i+1][j+2]==sum:\n",
    "                                        if  grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]==sum:\n",
    "                                            if  grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]==sum:\n",
    "                                                if  grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]==sum:\n",
    "                                                    num=num+1\n",
    "            return num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
